import static java.lang.Integer.rotateLeft;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-09-01
 * Time: 15:10
 */
public class AvlTree {
    //    AVL树节点的定义
    public static class AvlTreeNode {

        public int val = 0; //具体数值
        public AvlTreeNode parent = null; //节点的父节点
        public AvlTreeNode left = null; //节点的左节点
        public AvlTreeNode right = null; //节点的右节点

        public int bf = 0; //平衡因子

        public AvlTreeNode(int val) {
            this.val = val;
        }
    }

    public AvlTreeNode root;

    /*
    * 插入*/
    public boolean insert(int val) {
        AvlTreeNode node = new AvlTreeNode(val);
        if (root == null) {
            root = node;
            return true;
        }
        AvlTreeNode parent = null;
        AvlTreeNode cur = root;
        while (cur != null) {
            if (cur.val < val) {
                parent = cur;
                cur = cur.right;
            } else if (cur.val == val) {
                return false;
            } else {
                parent = cur;
                cur = cur.left;
            }
        }
        if (parent.val < val) {
            parent.right = node;
        } else {
            parent.left = node;
        }
        node.parent = parent;
        cur = node;
        // 平衡因子 的修改
        while (parent != null) {
            //先看cur是parent的左还是右  决定平衡因子是++还是--
            if (cur == parent.right) {
                //如果是右树，那么右树高度增加 平衡因子++
                parent.bf++;
            } else {
                //如果是左树，那么左树高度增加 平衡因子--
                parent.bf--;
            }
            //检查当前的平衡因子 是不是绝对值 1  0  -1
            if (parent.bf == 0) {
                //说明已经平衡了
                //AVL树的任何子树（非空）都是AVL树
                return true;
            } else if (parent.bf == 1 || parent.bf == -1) {
                //继续向上去修改平衡因子
                cur = parent;
                parent = cur.parent;
            } else {
                if (parent.bf == 2) {//右树高-》需要降低右树的高度
                    if (cur.bf == 1) {
                        //左旋
                        rotateLeft(parent);
                    } else {
                        rotateRL(parent);
                    }
                }else {
                    if (cur.bf == -1) {
                        //右旋
                        rotateRight(parent);
                    } else {
                        //左右旋
                        rotateLR(parent);
                    }
                }
                //上述代码走完就平衡了
                break;
            }
        }
        return true;
    }

    /**
     * 左边过高
     * 左单旋
     * 将左边旋下来
     * @param parent
     */
    private void rotateLeft(AvlTreeNode parent) {
        AvlTreeNode subR = parent.right;
        AvlTreeNode subRL = subR.left;

        subR.left = parent;
        if (subRL != null) {
            subRL.parent = parent;
        }
        parent.right = subRL;

        AvlTreeNode pParent = parent.parent;
        parent.parent = subR;

        if (root == parent) {
            root = subR;
            root.parent = null;
        } else {
            if (pParent.left == parent) {
                pParent.left = subR;
            } else {
                pParent.right = subR;
            }
            subR.parent = pParent;
        }

        subR.bf = parent.bf = 0;
    }

    /**
     * 右边过高
     * 右单旋
     * 将右边旋下来
     * @param parent
     */

    private void rotateRight(AvlTreeNode parent) {
        AvlTreeNode subL = parent.left;
        AvlTreeNode subLR = subL.right;

        parent.left = subLR;
        ////没有subLR
        if (subLR != null) {
            subLR.parent = parent;
        }
        subL.right = parent;

        //必须先记录
        AvlTreeNode pParent = parent.parent;
        parent.parent = subL;


        //检查 当前是不是就是根节点
        if (parent == root) {
            root = subL;
            root.parent = null;
        } else {
            //不是根节点，判断这棵子树是左子树还是右子树
            if (pParent.left == parent) {
                pParent.left = subL;
            } else {
                pParent.right = subL;
            }
            subL.parent = pParent;
        }
        subL.bf = 0;
        parent.bf = 0;
    }

    /**
     * 左右双旋
     *
     * @param parent
     */
    private void rotateLR(AvlTreeNode parent) {
        AvlTreeNode subL = parent.left;
        AvlTreeNode subLR = subL.right;
        int bf = subLR.bf;

        rotateLeft(subL);
        rotateRight(parent);
        if (bf == -1) {
            subL.bf = 0;
            subLR.bf = 0;
            parent.bf = 1;
        } else if (bf == 1) {
            subL.bf = -1;
            subLR.bf = 0;
            parent.bf = 0;
        }
    }

    private void rotateRL(AvlTreeNode parent) {
        AvlTreeNode subR = parent.right;
        AvlTreeNode subRL = subR.left;
        int bf = subRL.bf;

        rotateRight(parent.right);
        rotateLeft(parent);

        if (bf == 1) {
            parent.bf = -1;
            subR.bf = 0;
            subRL.bf = 0;
        } else if (bf == -1) {
            parent.bf = 0;
            subR.bf = 1;
            subRL.bf = 0;
        }
    }

    //中序遍历的结果是有序的 就能说明当前树 一定是AVL树吗？  不一定的
    public void inorder(AvlTreeNode root) {
        if (root == null) return;
        inorder(root.left);
        System.out.print(root.val + "  ");
        inorder(root.right);
    }

    private int height(AvlTreeNode root) {
        if (root == null) return 0;
        int leftH = height(root.left);
        int rightH = height(root.right);

        return leftH > rightH ? leftH + 1 : rightH + 1;
    }


//    验证其为平衡树
//    每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
//    节点的平衡因子是否计算正确

    public boolean isBalanced(AvlTreeNode root) {
        if (root == null) return true;
        int leftH = height(root.left);
        int rightH = height(root.right);

        if (rightH - leftH != root.bf) {
            System.out.println("这个节点：" + root.val + " 平衡因子异常");
            return false;
        }

        return Math.abs(leftH - rightH) <= 1
                && isBalanced(root.left)
                && isBalanced(root.right);
    }

    
}
